package likou.jindian;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/26 10:33
 */
public class _03_04_MyQueue {
    public static void main(String[] args) {
        _03_04_MyQueue queue = new _03_04_MyQueue();

        queue.push(1);
        queue.push(2);
        System.out.println(queue.peek());
        System.out.println(queue.pop());
        System.out.println(queue.empty());
    }

    int[] stack1;
    int[] stack2;
    int size = 8;
    int length = 0;

    /**
     * Initialize your data structure here.
     */
    public _03_04_MyQueue() {
        stack1 = new int[size + 1];//第一位存储栈的当前数量
        stack2 = new int[size + 1];
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        length++;
        if (stack1[0] == size) {
            if (stack2[0] == size) {
                //扩容并存储
                size = size << 1;
                int[] tmp = new int[size];
                System.arraycopy(stack1, 0, tmp, 0, (size >> 1));
                stack1 = tmp;
            } else if (stack2[0] == 0) {
                //stack1中元素移入stack2
                onetotwo(stack1, stack2);
            }
        }
        stack1[0]++;
        stack1[stack1[0]] = x;
        //&&stack1[0] > size / 2
        if (stack1[0] / 2 > stack2[0] && stack2[0] < size / 2 && stack2[0] + stack1[0] <= size) {
            //stack1中元素移入stack2
            onetotwo(stack1, stack2);
        }
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (length == 0) {
            return -1;
        }
        if (stack2[0] == 0) {
            //stack1中元素移入stack2
            onetotwo(stack1, stack2);
        }
        int res = stack2[stack2[0]];
        stack2[0]--;
        length--;
        return res;
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (length == 0) {
            return -1;
        }
        if (stack2[0] > 0) {
            return stack2[stack2[0]];
        }
        //stack1中元素移入stack2
        onetotwo(stack1, stack2);

        return stack2[stack2[0]];
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return length == 0;
    }

    public void onetotwo(int[] stack1, int[] stack2) {
        if (stack1[0] + stack2[0] <= size) {
            int[] tmp = Arrays.copyOf(stack2, stack2[0] + 1);
            //把stack1内容全部压入stack2栈
            stack2[0] = 0;
            while (stack1[0] > 0 && stack2[0] < size) {
                stack2[0]++;
                stack1[0]--;
                stack2[stack2[0]] = stack1[stack1[0]+1];
            }
            //把原stack2中的内容，直接放在当前stack2上面
            for (int i = 1; i < tmp.length; i++) {
                stack2[0]++;
                stack2[stack2[0]] = tmp[i];
            }
        }
    }
}
